package Aleehot100;

/**
 * ClassName: c085
 * Package: Aleehot100
 * Description: 322. 零钱兑换
 *
 * @Author BCXJ
 * @Create 2025/9/8 08:54
 * @Version 1.0
 * @Since 1.0
 */
public class c085 {
    public static void main(String[] args) {
        int[] arr = {1,2,5};
        System.out.println(coinChange(arr, 11));
    }

    //
    public static int coinChange(int[] coins, int amount) {
        // dp[i] 凑出钱为i的最少的硬币数量
        int[] dp = new int[amount + 1];

        // 初始化
        for (int i = 0; i < dp.length; i++) {
            dp[i] = amount + 1; // 代表无穷大
        }

        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if(coin <= i) {
                    dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
                }
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }

}
